﻿/*
 * Authors:    Kęstutis Džiautas
 *             Edmundas Matusevičius
 * University: VU, MIF, SE, 4 course
 * Date:       2010-11-20
 * Version:    1.1
 */

using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;

namespace SyntaxAnalizer {
    class ParseTable {
        public ParseTable() {
            grammarGraph = new Graph();

            nodesInDefinition = new Dictionary<string, Dictionary<string, ArrayList>>();

            first = new Dictionary<string, ArrayList>();
            follow = new Dictionary<string, ArrayList>();

            allTerminals = new ArrayList();
            allNonTerminals = new ArrayList();

            constructParseTable();
        }

        /// <summary>
        /// Returns cell data from table, identified by row and column.
        /// </summary>
        /// <param name="row">From which row to get data.</param>
        /// <param name="column">From which column to get data.</param>
        /// <returns>Data in cell identified by row and column.</returns>
        public ArrayList getCellData(string row, string column) {
            if (!allNonTerminals.Contains(row)) {
                return null;
            }
            if (!allTerminals.Contains(column)) {
                return null;
            }

            int firstIndex = allNonTerminals.IndexOf(row);
            int secondIndex = allTerminals.IndexOf(column);

            return parseTable[firstIndex, secondIndex];
        }

        /// <summary>
        /// Constructs parse table.
        /// </summary>
        private void constructParseTable() {
            // find all nodes in definitions
            constructNodesInDefinition();

            // find all first and follow terminals
            constructFirstAndFollow();

            // find all terminals and nonterminals
            constructTerminalAndNonTerminals();

            // prepare parse table
            parseTable = new ArrayList[allNonTerminals.Count, allTerminals.Count];

            // going through all nonterminals in grammar
            foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                // first node in one definition alternative
                GraphNode definitionNode = keyValuePair.Value;

                // parse table row's index
                int firstIndex = allNonTerminals.IndexOf(keyValuePair.Key);

                // going through all nonterminal's definition alternatives
                while (definitionNode.AltDef != null) {
                    // fill parse table with data
                    fillParseTable(firstIndex, definitionNode, keyValuePair.Key);

                    // get next alternative definition's start node
                    definitionNode = definitionNode.AltDef;
                }

                // fill parse table with data
                fillParseTable(firstIndex, definitionNode, keyValuePair.Key);
            }

            //// ATTENTION!
            //// print first/follow of one nonterminal
            ////GraphNode node = getGraphNodeDefinition("<Param End>");
            ////ArrayList list = getNodeAllFirstTerminals(node);
            //ArrayList list = getNodeAllFollowTerminals("<Params>");
            //for (int i = 0; i < list.Count; i++) {
            //    Console.Write(list[i] + " ");
            //}
            //Console.WriteLine();
            //Console.WriteLine("DONE");
            //Console.ReadLine();

            //// ATTENTION!
            //// print all First/Follow
            //foreach (KeyValuePair<string, ArrayList> keyValuePair in follow) {
            //    Console.WriteLine(keyValuePair.Key);

            //    foreach (string firstTerminal in keyValuePair.Value) {
            //        Console.Write(firstTerminal + " ");
            //    }
            //    Console.WriteLine("\n");
            //}
            //Console.WriteLine("\nGood news: we have DONE it.");
            //Console.ReadLine();

            //// ATTENTION!
            //// print all terminals/nonterminals
            //foreach (string terminal in allTerminals) {
            //    Console.Write(terminal + " ");
            //}
            //Console.WriteLine();
            //foreach (string nonTerminal in allNonTerminals) {
            //    Console.Write(nonTerminal + " ");
            //}
            //Console.WriteLine();
            //Console.ReadLine();

            //// ATTENTION!
            //// write to file all First/Follow
            ////StreamWriter fFile = new StreamWriter("first.txt");
            //StreamWriter fFile = new StreamWriter("follow.txt");

            //foreach (KeyValuePair<string, ArrayList> keyValuePair in follow) {
            //    fFile.WriteLine(keyValuePair.Key);

            //    foreach (string firstTerminal in keyValuePair.Value) {
            //        fFile.Write(firstTerminal + " ");
            //    }
            //    fFile.WriteLine("\n");
            //}

            //fFile.Close();

            //// ATTENTION!
            //// write to file parse table
            //StreamWriter file = new StreamWriter("table.txt");

            //file.Write(String.Format("{0,25:000}", "") + " |");
            //foreach (string terminal in allTerminals) {
            //    file.Write(String.Format("{0,60:000}", terminal) + " |");
            //}
            //file.WriteLine();
            //file.WriteLine(new String('-', (allTerminals.Count * 62) + 27));
            //for (int i = 0; i < allNonTerminals.Count; i++) {
            //    file.Write(String.Format("{0,25:000}", allNonTerminals[i]) + " |");
            //    for (int j = 0; j < allTerminals.Count; j++) {
            //        if (parseTable[i, j] != null) {
            //            file.Write(String.Format("{0,60:000}", string.Join("", parseTable[i, j].ToArray())) + " |");
            //        } else {
            //            file.Write(String.Format("{0,60:000}", "") + " |");
            //        }
            //    }
            //    file.WriteLine();
            //}

            //file.Close();

            //// ATTENTION!
            //Console.WriteLine("Hoory! We have finished successfully.");
            //Console.ReadLine();
        }

        /// <summary>
        /// Fills parse table cell with correct data.
        /// </summary>
        /// <param name="firstIndex">Index of parse table row, which should be filled.</param>
        /// <param name="definitionNode">First nonterminal's alternative's first node.</param>
        /// <param name="key">Nonterminal's name.</param>
        private void fillParseTable(int firstIndex, GraphNode definitionNode, string key) {
            // terminal index in parse table
            int secondIndex;

            // definition node iterator
            GraphNode definitionNodeIterator = definitionNode;
            // list of all nodes in one definition alternative
            ArrayList definitionNodeList = new ArrayList();

            // going through all definion's nodes and adding to definition node list
            while (definitionNodeIterator.Next != null) {
                definitionNodeList.Add(definitionNodeIterator.Def);
                definitionNodeIterator = definitionNodeIterator.Next;
            }
            definitionNodeList.Add(definitionNodeIterator.Def);

            // if terminal in definition found
            if ((definitionNode.Def.Equals("<Id>") ||
                 definitionNode.Def.Equals("<Dec>") ||
                 definitionNode.Def.Equals("<Float>") ||
                 definitionNode.Def.Equals("<Char Def>") ||
                 definitionNode.Def.Equals("<String Def>")) ||
                (!definitionNode.Def.StartsWith("<") &&
                 !definitionNode.Def.Equals("#"))) {
                secondIndex = allTerminals.IndexOf(definitionNode.Def);

                // if cell is not null, then grammar error
                if (parseTable[firstIndex, secondIndex] == null) {
                    parseTable[firstIndex, secondIndex] = definitionNodeList;
                } else {
                    Console.WriteLine("ERROR in grammar [at " + key + " in " + definitionNode.Def + "]");
                }
            } else {
                if (!definitionNode.Def.Equals("#")) {
                    foreach (string firstTerminal in first[definitionNode.Def]) {
                        secondIndex = allTerminals.IndexOf(firstTerminal);

                        // if cell is not null, then grammar error
                        if (parseTable[firstIndex, secondIndex] == null) {
                            parseTable[firstIndex, secondIndex] = definitionNodeList;
                        } else {
                            Console.WriteLine("ERROR in grammar [at " + key + " in " + definitionNode.Def + "]");
                        }
                    }
                } else {
                    foreach (string followTerminal in follow[key]) {
                        secondIndex = allTerminals.IndexOf(followTerminal);

                        // if cell is not null, then grammar error
                        if (parseTable[firstIndex, secondIndex] == null) {
                            parseTable[firstIndex, secondIndex] = new ArrayList() { "#" };
                        } else {
                            Console.WriteLine("ERROR in grammar [at " + key + " in " + followTerminal + "]");
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Returns all nodes that are used in other non-terminals definitions.
        /// </summary>
        /// <param name="searchInName">In which non-terminal's definition to search.</param>
        /// <param name="searchForName">For what non-terminal to search.</param>
        /// <returns>Array list of nodes in definitions.</returns>
        private ArrayList getNodesInDefinition(string searchInName, string searchForName) {
            ArrayList nodesList = new ArrayList();
            GraphNode temporaryNode = new GraphNode();
            GraphNode searchInNode = new GraphNode();

            grammarGraph.defDictionary.TryGetValue(searchInName, out searchInNode);

            // go through all alternatives
            while (searchInNode.AltDef != null) {
                temporaryNode = searchInNode;

                // go through all definition
                while (temporaryNode.Next != null) {
                    // add to return list if found
                    if (temporaryNode.Def.Equals(searchForName)) {
                        nodesList.Add(temporaryNode);
                    }

                    // set for next definition element
                    temporaryNode = temporaryNode.Next;
                }

                // add to return list if found
                if (temporaryNode.Def.Equals(searchForName)) {
                    nodesList.Add(temporaryNode);
                }

                // set for next alternative
                searchInNode = searchInNode.AltDef;
            }

            // search last alternative's definition
            while (searchInNode.Next != null) {
                // add to return list if found
                if (searchInNode.Def.Equals(searchForName)) {
                    nodesList.Add(searchInNode);
                }

                // set for next definition element
                searchInNode = searchInNode.Next;
            }

            // add to return list if found
            if (searchInNode.Def.Equals(searchForName)) {
                nodesList.Add(searchInNode);
            }

            return nodesList;
        }

        /// <summary>
        /// Returns list of first terminals in node's definition route.
        /// </summary>
        /// <param name="node">Node in which search should be done.</param>
        /// <returns>Array list of first terminals.</returns>
        private ArrayList getNodeAllFirstTerminals(GraphNode node) {
            ArrayList list = new ArrayList();
            ArrayList temporaryList = new ArrayList();

            // search within all alternatives
            if (node.AltDef != null) {
                // go deeper into recursion
                temporaryList = getNodeAllFirstTerminals(node.AltDef);

                // copy results to return list
                copyToList(temporaryList, ref list);
            }

            // if found terminal
            if (!node.Def.StartsWith("<")) {
                list.Add(node.Def);
            } else {
                // search with all next definitions
                if (node.NextDef != null) {
                    // go deeper into recursion
                    temporaryList = getNodeAllFirstTerminals(node.NextDef);

                    // copy results to return list
                    copyToList(temporaryList, ref list);
                } else {
                    GraphNode temporaryNode = new GraphNode();

                    // go deeper into recursion
                    grammarGraph.defDictionary.TryGetValue(node.Def, out temporaryNode);

                    // check if not a basic terminal like id, integer etc.
                    if (temporaryNode == null) {
                        list.Add(node.Def);
                    } else {
                        temporaryList = getNodeAllFirstTerminals(temporaryNode);
                    }

                    // copy results to return list
                    copyToList(temporaryList, ref list);
                }
            }

            return list;
        }

        /// <summary>
        /// Returns list of follow terminals in node's definition route.
        /// </summary>
        /// <param name="nodeName">Node name for which search should be done.</param>
        /// <returns>Array list of follow terminals.</returns>
        private ArrayList getNodeAllFollowTerminals(string nodeName) {
            ArrayList list = new ArrayList();
            ArrayList temporaryList = new ArrayList();
            ArrayList nodesList = new ArrayList();

            Dictionary<string, ArrayList> tmp = new Dictionary<string, ArrayList>();
            nodesInDefinition.TryGetValue(nodeName, out tmp);

            foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                //nodesList = getNodesInDefinition(keyValuePair.Key, nodeName);
                tmp.TryGetValue(keyValuePair.Key, out nodesList);

                foreach (GraphNode node in nodesList) {
                    if (node.Next != null) {
                            // possibly non-terminal or terminal
                            if (node.Next.Def.StartsWith("<")) {
                                if (first.ContainsKey(node.Next.Def)) {
                                    temporaryList = first[node.Next.Def];
                                }

                                // copy results to return list
                                copyToList(temporaryList, ref list);

                                // if contains empty, add all parent's follow
                                if (temporaryList.Contains("#")) {
                                    if (follow.ContainsKey(keyValuePair.Key)) {
                                        temporaryList = follow[keyValuePair.Key];
                                    } else {
                                        temporaryList = getNodeAllFollowTerminals(keyValuePair.Key);
                                        follow.Add(keyValuePair.Key, temporaryList);
                                    }

                                    // copy results to return list
                                    copyToList(temporaryList, ref list);
                                    list.Remove("#");
                                }
                            } else {
                                // before add check for repeat
                                if (!list.Contains(node.Next.Def)) {
                                    list.Add(node.Next.Def);
                                }
                            }
                    } else {
                        // if declaration not equal to definition
                        if (!node.Def.Equals(keyValuePair.Key)) {
                            if (follow.ContainsKey(keyValuePair.Key)) {
                                temporaryList = follow[keyValuePair.Key];
                            } else {
                                temporaryList = getNodeAllFollowTerminals(keyValuePair.Key);
                                follow.Add(keyValuePair.Key, temporaryList);
                            }

                            // copy results to return list
                            copyToList(temporaryList, ref list);
                        }
                    }
                }
            }
            
            return list;
        }

        /// <summary>
        /// Copy one list to other.
        /// </summary>
        /// <param name="fromList">List from which to copy.</param>
        /// <param name="toList">List to which to copy.</param>
        private void copyToList(ArrayList fromList, ref ArrayList toList) {
            for (int i = 0; i < fromList.Count; i++) {
                // check if value is not repeating
                if (!toList.Contains(fromList[i])) {
                    toList.Add(fromList[i]);
                }
            }
        }

        /// <summary>
        /// Fills up nodesInDefinition dictionary.
        /// </summary>
        private void constructNodesInDefinition() {
            string[] keys = new string[grammarGraph.defDictionary.Count];

            grammarGraph.defDictionary.Keys.CopyTo(keys, 0);

            foreach (string key in keys) {
                Dictionary<string, ArrayList> nodesList = new Dictionary<string, ArrayList>();
                foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                    nodesList.Add(keyValuePair.Key, getNodesInDefinition(keyValuePair.Key, key));
                }

                nodesInDefinition.Add(key, nodesList);
            }
        }

        /// <summary>
        /// Fills up first and follow dictionaries.
        /// </summary>
        private void constructFirstAndFollow() {
            string nodeName;
            GraphNode node;

            // find all first and follow for each nonterminal in grammar

            foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                nodeName = keyValuePair.Key;
                node = keyValuePair.Value;

                first.Add(nodeName, getNodeAllFirstTerminals(node));
            }

            foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                nodeName = keyValuePair.Key;

                if (!follow.ContainsKey(nodeName)) {
                    follow.Add(nodeName, getNodeAllFollowTerminals(nodeName));
                }
            }
        }

        /// <summary>
        /// Fills up allTerminals and allNonTerminals dictionaries.
        /// </summary>
        private void constructTerminalAndNonTerminals() {
            // find all terminals
            foreach (KeyValuePair<string, ArrayList> keyValuePair in follow) {
                foreach (string nonTerminal in keyValuePair.Value) {
                    if (!allTerminals.Contains(nonTerminal)) {
                        allTerminals.Add(nonTerminal);
                    }
                }
            }

            foreach (KeyValuePair<string, ArrayList> keyValuePair in first) {
                foreach (string nonTerminal in keyValuePair.Value) {
                    if (!allTerminals.Contains(nonTerminal)) {
                        allTerminals.Add(nonTerminal);
                    }
                }
            }

            // find all nonterminals
            foreach (KeyValuePair<string, GraphNode> keyValuePair in grammarGraph.defDictionary) {
                allNonTerminals.Add(keyValuePair.Key);
            }
        }

        /// <summary>
        /// Get all nodes in definitions.
        /// </summary>
        private Dictionary<string, Dictionary<string, ArrayList>> nodesInDefinition;
        /// <summary>
        /// All first terminals in nonterminal definition.
        /// </summary>
        private Dictionary<string, ArrayList> first;
        /// <summary>
        /// All follow terminals in nonterminal definition.
        /// </summary>
        private Dictionary<string, ArrayList> follow;
        /// <summary>
        /// All terminals in grammar.
        /// </summary>
        private ArrayList allTerminals;
        /// <summary>
        /// All nonterminals in grammar;
        /// </summary>
        private ArrayList allNonTerminals;
        /// <summary>
        /// Parse table for grammar analyze.
        /// </summary>
        private ArrayList[,] parseTable;
        /// <summary>
        /// Programming language grammar's graph.
        /// </summary>
        private Graph grammarGraph;
    }
}
